/*
 * AlphaBetaWithMemory.cpp
 *
 *  Created on: 21/06/2011
 *      Author: frandres
 */

#include "MTDF.h"

MTDF::MTDF() {
	transpositionTable = new Hash();

}

MTDF::~MTDF() {
	Hash::iterator eraser = transpositionTable->begin();
	for(; eraser != transpositionTable->end(); eraser++)
		delete (eraser->second);

	delete(transpositionTable);
}

/*
 * El driver MTDF.
 */
int  MTDF::mtdf(OthelloTranspositionTableNode * n, int f , int d, bool isBlack){
	gameValue = f;
	int beta;
	int upperbound = MAX_VALUE ;
	int lowerbound = MIN_VALUE;
	OthelloTranspositionTableNode * clone;
	do{
		if (gameValue == lowerbound){
			beta = gameValue+1;
		}else {
			beta = gameValue;
		}
		n->cloneNode(clone);
		gameValue = run(clone,beta-1,beta,d,isBlack);

		if (gameValue<beta){
			upperbound = gameValue;
		} else{
			lowerbound = gameValue;
		}

	} while (lowerbound <upperbound);

	delete(n);
}

int MTDF::run(OthelloTranspositionTableNode * n, int alpha , int beta , int d, bool isBlack){

	Hash::iterator pos = transpositionTable->find(n->getKey());
	bool foundInTT = false; /* Encontrado en la tabla de transposicion */

	for(; pos != transpositionTable->end() && n->getKey() == pos->first  /* No se ha terminado de recorrer. */
			; pos++)
	{
		if(n->compare(pos->second)) /* Si son nodos iguales. */
		{
			foundInTT = true;
			break;
		}

	}

	OthelloTranspositionTableNode * nodeInTable ;

	if (foundInTT){
		nodeInTable = (OthelloTranspositionTableNode *) pos->second;
		if (nodeInTable->isLowerSet()){
			if (nodeInTable->getLowerBound()>= beta){
				delete(n);
				return nodeInTable->getLowerBound();
			}
			alpha = MAX(alpha,nodeInTable->getLowerBound());
		}

		if (nodeInTable->isUpperSet()){
			if (nodeInTable->getUpperBound()<= alpha){
				delete(n);
				return nodeInTable->getUpperBound();
			}else {
				beta = MIN(beta,nodeInTable->getUpperBound());
			}
		}


	} else{
		nodeInTable = n; // Para actualizar valores.
	}

	int g = 0;

	if (n->isTerminal()) {  /* Se trata de una hoja */
		g = n->evaluate();

	}else {

		// Es el nodo a usar en la llamada recursiva.
		OthelloTranspositionTableNode * son;

		// Determina si el jugador pasa o no.
		bool playerPasses = true;

		int r =0;// Value

		if (!isBlack){ // Juega el blanco y es max.
			g = MIN_VALUE;//
			int a = alpha;

			for (int i = 0; i < 36 && g < beta ; i++){

				if (n->generateSon(isBlack,i,son)){ // Jugar en la posicion i es valido y por ende un hijo.
					r = run(son,a,beta,d+1,!isBlack);
					g = MAX(g,r);
					a = MAX(a,g);
					playerPasses = false;
				}
			}

			if (playerPasses){
				n->cloneNode(son);
				r = run(son,a,beta,d+1,!isBlack);
				g = MAX(g,r);
				a = MAX(a,g);
			}
		}
		else {
			g = MAX_VALUE;
			int b = beta;

			//Generar hijos
			for (int i = 0; i < 36 && g > alpha ; i++){

				if (n->generateSon(isBlack,i,son)){ // Jugar en la posicion i es valido y por ende un hijo.
					r = run(son,alpha,b,d+1,!isBlack);
					g = MIN(g,r);
					b = MIN(b,g);
					playerPasses = false;
				} else{
				}
			}

			if (playerPasses){
				n->cloneNode(son);
				r = run(son,alpha,b,d+1,!isBlack);
				g = MIN(g,r);
				b = MIN(b,g);
			}
		}
	}


	/* Almacenamiento en la tabla de transposición. */

	/* Un fallo por resultado bajo implica una cota superior. */
	if (g <= alpha) {
		nodeInTable->setUpperBound(g);
	}
	/* Se encontró un valor minmax correcto. No debe ocurrir si se llama
	 * con una ventana 0.*/
	if (g >  alpha and g < beta){
		nodeInTable->setLowerBound(g);
		nodeInTable->setUpperBound(g);
	}

	/*  Un fallo por resultado alto implica una cota inferior. */
	if (g >= beta){
		nodeInTable->setLowerBound(g);
	}

	if (foundInTT) {
		delete(n);
	}else
	{ /* No está presente en la tabla. Hay que guardar el nodo completo en la tabla.*/
	if (numberOfNodes <= MAX_NUMBER_OF_NODES){
			transpositionTable->insert(Hash::value_type(n->getKey() , n));
			incrementNumberOfNodes();
		}
		else{

			delete(n);
		}
	}

	return g;
}
